import common.TreeNode;

public class isBalanced {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    //自底向上，先遍历在处理
    /**
     * 递归函数，用于计算从当前节点开始的子树的深度，如果子树不是平衡的，则返回-1
     * @param root 当前节点
     * @return 当前节点为根的子树的深度，如果不是平衡树则返回-1
     */
    private int recur(TreeNode root) {
        // 如果当前节点为空，说明已经到达树的底部，返回深度0
        if (root == null) return 0;

        // 递归计算左子树的深度
        int left = recur(root.left);
        // 如果左子树不是平衡的，直接返回-1
        if (left == -1) return -1;

        // 递归计算右子树的深度
        int right = recur(root.right);
        // 如果右子树不是平衡的，直接返回-1
        if (right == -1) return -1;

        // 判断当前节点的左右子树深度差是否小于2，如果是，则返回当前节点的深度（子树深度的最大值加1），否则返回-1
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}
